#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ElementType int


struct Node
{
    ElementType data;
    struct Node* next;
};
typedef struct Node node;

typedef struct LinkList
{
    node* head;
    int len;
}Llist;

node* CreateNode(ElementType element)
{
    node *newNode = (node*)malloc(sizeof(node));
    if(newNode == NULL)
    {
        printf("create node error!\n");
        return NULL;
    }
    newNode->data = element;
    newNode->next = NULL;
    return newNode;
}

void InitLlist(Llist *l)
{
    l->len = 0;
    l->head = CreateNode(0);
}

void InsertTail(Llist *l,ElementType element)
{
    node *newNode = CreateNode(element);
    node *TravelPoint = l->head;
    while(TravelPoint->next != NULL)
    {
        TravelPoint = TravelPoint->next;
    }
    TravelPoint->next = newNode;
    l->len++;
}

void InsertHead(Llist *l,ElementType element)
{
    node *newNode = CreateNode(element);
    newNode->next = l->head->next;
    l->head->next = newNode;
    l->len++;
}

void InsertByIndex(Llist *l,int index,ElementType element)
{
    if(index < 0 || index > l->len)
    {
        printf("插入位置非法!\n");
        return;
    }
    node *TravelPoint = l->head;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    node *newNode = CreateNode(element);
    newNode->next = TravelPoint->next;
    TravelPoint->next = newNode;
    l->len++;
}

void RemoveByIndex(Llist *l,int index)
{
    if(index < 0 || index >= l->len)
    {
        printf("删除位置非法!\n");
        return;
    }
    node *TravelPoint = l->head;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    node *freeNode = TravelPoint->next;
    TravelPoint->next = freeNode->next;
    free(freeNode);
    l->len--;
}

void RemoveByElement(Llist *l,ElementType element)
{
    node *TravelPoint = l->head;
    while(TravelPoint->next != NULL)
    {
        if(TravelPoint->next->data == element)
        {
            node *freeNode = TravelPoint->next;
            TravelPoint->next = freeNode->next;
            free(freeNode);
            l->len--;
        }
        else
        {
            TravelPoint = TravelPoint->next;
        }
    }
}

void UpdataByIndex(Llist *l,int index,ElementType element)
{
    if(index < 0 || index >= l->len)
    {
        printf("修改位置非法!\n");
        return;
    }
    node *TravelPoint = l->head;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    TravelPoint->next->data = element;
}

void UpdataByElement(Llist *l,ElementType oldValue,ElementType newValue)
{
    node *TravelPoint = l->head;
    while(TravelPoint->next != NULL)
    {
        if(TravelPoint->next->data == oldValue)
        {
            TravelPoint->next->data = newValue;
        }
        else
        {
            TravelPoint = TravelPoint->next;
        }
    }
}

ElementType *FindByIndex(Llist *l,int index)
{
    if(index < 0 || index >= l->len)
    {
        printf("查找位置非法!\n");
        return NULL;
    }
    node *TravelPoint = l->head;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    return &TravelPoint->next->data;
}

node* *FindByElement(Llist *l,ElementType element)
{
    node * *dyA = (node**)malloc(sizeof(node*) * (l->len + 1));
    if(dyA == NULL)
    {
        printf("malloc error!\n");
        return NULL;
    }
    int count = 0;
    node *TravelPoint = l->head;
    while(TravelPoint->next != NULL)
    {
        if(TravelPoint->next->data == element)
        {
            dyA[count] = TravelPoint->next;
            count++;
        }
        TravelPoint = TravelPoint->next;
    }
    dyA[count] = NULL;
    return dyA;
}

void Swap(ElementType *value1,ElementType *value2)
{
    ElementType temp = *value1;
    *value1 = *value2;
    *value2 = temp;
}

void FastSort(node* start,node *end)
{
    if(start == end)
        return;
    node *p1 = start;
    node *p2 = p1->next;

    while(p2 != end)
    {
        if(p2->data < start->data)
        {
            p1 = p1->next;
            Swap(&p1->data,&p2->data);
        }
        p2 = p2->next;
    }
    Swap(&start->data,&p1->data);
    FastSort(start,p1);
    FastSort(p1->next,p2);
}

void Reserve(Llist *l)
{
    if(l->len == 0 || l->len == 1)
        return;
    node *prev = NULL;
    node *cur = l->head->next;
    node *Next = cur->next;

    while(Next != NULL)
    {
        cur->next = prev;
        prev = cur;
        cur = Next;
        Next = cur->next;
    }
    cur->next = prev;
    l->head->next = cur;
}

node * Reserve2(node *n)
{
    if(n->next == NULL)
    {
        return n;
    }
    else
    {
        node *tail = Reserve2(n->next);
        n->next->next = n;
        n->next = NULL;
        return tail;
    }
}
    

Llist Merge(Llist *l1,Llist *l2)
{
    Llist list;
    InitLlist(&list);
    node *p1 = l1->head->next;
    node *p2 = l2->head->next;

    while(p1 != NULL && p2 != NULL)
    {
        if(p1->data > p2->data)
        {
            InsertTail(&list,p2->data);
            p2 = p2->next;
        }
        else
        {
            InsertTail(&list,p1->data);
            p1 = p1->next;
        }
    }
    while(p1 != NULL)
    {
        InsertTail(&list,p1->data);
        p1 = p1->next;
    }
    while(p2 != NULL)
    {
        InsertTail(&list,p2->data);
        p2 = p2->next;
    }
    return list;
}

struct Node* findAndModify(struct Node* node, ElementType target) 
{
    if (node == NULL) 
    {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = target;
        newNode->next = NULL;
        return newNode;
    }

    struct Node* prev = NULL;
    struct Node* current = node;

    while (current != NULL && current->data < target) 
    {
        prev = current;
        current = current->next;
    }

    if (current != NULL && current->data == target) 
    {
        // 找到元素，交换位置
        if (current->next != NULL) 
        {
            ElementType temp = current->data;
            current->data = current->next->data;
            current->next->data = temp;
        }
    } 
    else 
    {
        // 未找到元素，插入保持有序
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = target;

        if (prev == NULL) 
        {
            newNode->next = node;
            node = newNode;
        } 
        else 
        {
            newNode->next = prev->next;
            prev->next = newNode;
        }
    }

    return node;
}


void Dumplication(Llist *list)
{
    FastSort(list->head->next,NULL);
    node *TravelPoint = list->head;
    int count = 0;
    while(TravelPoint->next != NULL)
    {
        if(TravelPoint->data == TravelPoint->next->data)
        {
            RemoveByIndex(list,count);
        }
        else
        { 
            TravelPoint = TravelPoint->next;
            count++;
        }    
    }
}

Llist FindInsection(node *l1,node *l2)
{
    Llist list;
    InitLlist(&list);
    while(l1 != NULL && l2 != NULL)
    {
        if(l1->data == l2->data)
        {
            InsertTail(&list,l1->data);
            l1 = l1->next;
            l2 = l2->next;
        }
        else if(l1->data > l2->data)
        {
            l2 = l2->next;
        }
        else
        {
            l1 = l1->next;
        }
    }
    return list;
}

node* FindInsection2(node *l1,node *l2)
{
    node temp;
    node *tail = &temp;
    while(l1 != NULL && l2 != NULL)
    {
        if(l1->data == l2->data)
        {
            tail->next = l1;
            tail = tail->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        else if(l1->data > l2->data)
        {
            l2 = l2->next;
        }
        else
        {
            l1 = l1->next;
        }
    }
    tail->next = NULL;
    return temp.next;
}


void FreeLlist(Llist *l)
{
    while(l->head != NULL)
    {
        node *next = l->head->next;
        free(l->head);
        l->head = next;
    }
    l->len = 0;
}

void Travel(Llist *l)
{
    node *TravelPoint = l->head->next;
    while(TravelPoint != NULL)
    {
        printf("%d ",TravelPoint->data);
        TravelPoint = TravelPoint->next;
    }
    printf("\n");
}
int main()
{
    srand(time(NULL));
    Llist l;
    InitLlist(&l);
    for(int i = 1; i <= 10; i++)
    {
        InsertTail(&l,i);
    }
    //Travel(&l);
    // node** dyA = FindByElement(&l,23);
    // int count = 0;
    // while(dyA[count] != NULL)
    // {
    //     printf("%d ",dyA[count]->data);
    //     count++;
    // }
    // printf("\n");
    // free(dyA);
    RemoveByElement(&l,3);
    RemoveByElement(&l,6);
    FastSort(l.head->next,NULL);
    Travel(&l);
    //l.head->next = Reserve2(l.head->next);
    l.head->next = findAndModify(l.head->next,6);
    //Dumplication(&l);
    Travel(&l);

    // l.head->next = Reserve2(l.head->next);
    // Travel(&l);
    Llist l2;
    InitLlist(&l2);
    for(int i = 2; i <= 11; i++)
    {
        InsertTail(&l2,i);
    }
    FastSort(l2.head->next,NULL);
    Travel(&l2);

    l.head->next = FindInsection2(l.head->next,l2.head->next);
    Travel(&l);

    // Llist list;
    // InitLlist(&list);
    // list = Merge(&l,&l2);
    // Travel(&list);

    // Llist list;
    // InitLlist(&list);
    // list = FindInsection(l.head->next,l2.head->next);
    // Travel(&list);
    return 0;
}